1. Technical Field
The invention is related to data processing in finite element analysis, and in particular, to a technique for adapting hierarchical basis functions to inhomogeneous problems for preconditioning large optimization problems.
2. Related Art
Many finite element analysis problems, including many computer graphics problems, can be formulated as the solution of a set of spatially-varying linear or non-linear partial differential equations (PDEs). A few of the many such problems include computational photography algorithms such as high-dynamic range tone mapping, Poisson and gradient-domain blending, and colorization. Such problems also include various physically-based modeling problems such as elastic surface dynamics and the regularized solution of computer vision problems such as surface reconstruction, optic flow, and shape from shading. Techniques for addressing such continuous variational problems are well known to those skilled in the art.
For example, the discretization of these continuous variational problems using finite element or finite difference techniques yields large sparse systems of linear equations. Direct methods for solving sparse systems become inefficient for large multi-dimensional problems because of excessive amounts of fill-in that occurs during the solution. Therefore, in most cases, iterative solutions are a better choice. Unfortunately, as the problems become larger, the performance of iterative algorithms usually degrades due to the increased condition number of the associated systems. To address this problem, two different classes of techniques, both based on multi-level (hierarchical) representations, have traditionally been used to accelerate the convergence of iterative techniques.
For example, the first of these convergence acceleration techniques are generally referred to as multigrid techniques. In general, these multigrid techniques interpolate between different levels of resolution in an effort to alternately reduce the low- and high-frequency components of the resulting error. Unfortunately, such techniques work best for smoothly varying (homogeneous) problems, which is often not the case for many finite element or computer graphics applications.
The second class convergence acceleration techniques includes optimization algorithms such as a conjugate gradient preconditioned using a variety of techniques. Among these techniques, multi-level preconditioners such as hierarchical basis functions and wavelets are well suited for graphics applications because they exploit the natural multi-scale nature of many visual problems.
Unfortunately, while multi-level preconditioners have proven to be quite effective at accelerating the solution of such tasks, some problems remain. For example, the choice of basis functions and the number of levels is problem-dependent. In addition, such algorithms perform poorly on problems with large amounts of inhomogeneity, such as local discontinuities or irregularly spaced data.